package com.leetcode;

import java.util.*;

/**
 * 398. 随机数索引
 * 水塘抽样
 * 2022-04-25 每日一题
 *
 * @author fy
 * @date 2022/4/25 14:10
 */
public class Solution398_1 {

    class Solution {

        private int[] nums;
        private Random random;

        public Solution(int[] nums) {
            this.nums = nums;
            this.random = new Random();
        }

        public int pick(int target) {
            int index = -1;
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                int num = nums[i];
                if (num == target) {
                    count++;
                    if (random.nextInt(count) == 0) {
                        index = i;
                    }
                }
            }
            return index;
        }
    }

}
